package leetco.test;

/**
 * 反转链表
 */
public class Solution_206 extends ListNode {

    public static void main(String[] args) {
        ListNode node = createNode(1, 2, 3, 4, 5);
        System.out.println(node);
        System.out.println(reverseList(node));
    }

    /**
     * 假设链表为 1→2→3→∅，我们想要把它改成 3∅←1←2←3。
     * 在遍历链表时，将当前节点的 next 指针改为指向前一个节点。
     * 由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。
     * 在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
     */
    public static ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;
        while (cur != null) {
            ListNode next = cur.next; // 遍历用 1
            cur.next = prev;
            prev = cur;
            cur = next; // 遍历 指向下个节点 2
        }
        return prev;
    }
}

